package com.hot100;

import java.util.ArrayList;
import java.util.List;

public class Solution658 {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int i = 0;
        int j = arr.length - 1;
        while (i < j) {
            int mid = (i + j) >> 1;
            if (arr[mid] < x) i = mid + 1;
            else if (arr[mid] >= x) j = mid;
        }
        i = i - 1 >= 0 && Math.abs(arr[i - 1] - x) <= Math.abs(arr[i] - x) ? i - 1 : i;
        int start = i - 1;
        int end = i + 1;
        while (end - start - 1 < k) {
            if (end < arr.length && start >= 0) {
                if (Math.abs(arr[end] - x) < Math.abs(arr[start] - x)) end++;
                else start--;
            } else if (start >= 0) start--;
            else end++;
        }
        List<Integer> res = new ArrayList<>();
        for (int l = start + 1; l < end; l++) {
            res.add(arr[l]);
        }
        return res;
    }
}
